/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-08-20
 * Time: 23:46
 */

class Solution3 {
    public void reorderList(ListNode head) {
        // 1.边界条件判断
        if(head == null || head.next == null || head.next.next == null) {
            return;
        }

        // 找到中间节点
        ListNode slow = head,fast = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 分割成两部分
        ListNode cur = slow.next;
        slow.next = null;

        // 逆序
        ListNode head2 = new ListNode(0);

        while(cur != null) {
            ListNode cur1 = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = cur1;
        }

        // 合并
        ListNode ret = new ListNode(0);
        ListNode pre = ret;

        ListNode cur1 = head;
        ListNode cur2 = head2.next;

        while(cur1 != null) {
            pre.next = cur1;
            pre = cur1;
            cur1 = cur1.next;
            if(cur2 != null) {
                pre.next = cur2;
                pre = cur2;
                cur2 = cur2.next;

            }
        }
    }
}
